Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Lowest Common Ancestor of a Binary Search Tree

Problem Statement

Given a binary search tree (BST) and two of its nodes, find the node that is the lowest common ancestor (LCA) of the two given nodes. The LCA of two nodes is the node that lies in between the two nodes in terms of value and is the furthest from the root. In other words, it's the deepest node where the two nodes diverge in the tree. Remember, in a BST, nodes have unique values.

Examples

  • Input:
    • BST: [6,2,8,0,4,7,9,null,null,3,5]
    • Node 1: 2
    • Node 2: 8
  • Expected Output: 6
Image
  • Justification: The nodes 2 and 8 are on the left and right children of node 6. Hence, node 6 is their LCA.
  • Input:
    • BST: [6,2,8,0,4,7,9,null,null,3,5]
    • Node 1: 0
    • Node 2: 3
  • Expected Output: 2
Image
  • Justification: The nodes 0 and 3 are on the left and right children of node 2, which is the closest ancestor to these nodes.
  • Input:
    • BST: [6,2,8,0,4,7,9,null,null,3,5]
    • Node 1: 4
    • Node 2: 5
  • Expected Output: 4
Image
  • Justification: Node 5 is the right child of node 4. Hence, the LCA is node 4 itself.

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Solution

The binary search tree property helps us find the solution without exploring the entire tree. Each node, starting from the root, provides a range based on its value that can determine where the two nodes are located.

  1. Starting at the Root: Begin at the root of the BST.

  2. Determining Direction: If the values of both nodes are greater than the current root node's value, then the LCA must be in the right subtree. If the values are both less, then the LCA is in the left subtree.

  3. Divergence Point: If one node's value is less than the root's value and the other node's value is greater (or if one of them matches the root's value), then the current root is the LCA, since the path to reach both nodes diverges from here.

  4. Iterative Search: Repeat the process iteratively on the selected subtree (either left or right) until you find the LCA.

Algorithm Walkthrough

Using the first example input:

  • BST: [6,2,8,0,4,7,9,null,null,3,5]
  • Node 1: 2
  • Node 2: 8

Steps:

  • Start at root which is 6.
  • Both 2 and 8 are on different sides of 6 (2 on the left and 8 on the right).
  • Therefore, 6 is the lowest common ancestor.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

The algorithm traverses the BST in a single path, either going left or right, but never both. Therefore:

  • Time Complexity: O(h), where h is the height of the BST.
  • pace Complexity: O(1) since we only used a constant amount of space.
Lowest Common Ancestor of a Binary Search Tree (medium)
'K' Closest Points to the Origin (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Algorithm Walkthrough

Code

Complexity Analysis